import java.util.Stack;

/**
 * @author LKQ
 * @date 2021/12/30 10:14
 * @description
 */
public class Solution {
    public static void main(String[] args) {

    }

    public ListNode middleNode(ListNode head) {
        // 借助栈
        Stack<ListNode> stack = new Stack<>();
        int count = 0;
        while (head != null) {
            stack.push(head);
            head = head.next;
            count++;
        }
        int half = count % 2 ==0 ? count / 2 - 1 : count / 2;
        while (half > 0) {
            stack.pop();
            half--;
        }
        return stack.peek();
    }

    public ListNode middleNode2(ListNode head) {
        // 不借助栈
        int count = 0;
        ListNode temp = head;
        while (temp != null) {
            count++;
            temp = temp.next;
        }
        int half = count / 2;
        while (half > 0) {
            head = head.next;
            half--;
        }
        return head;
    }


}
class ListNode {
    int val;
    ListNode next;
    ListNode() {

    }
    ListNode(int val) {
        this.val = val;
    }
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
